//: Playground - noun: a place where people can play

import UIKit

public class TreeNode {
    public var val: Int;
    public var left: TreeNode?;
    public var right: TreeNode?;
    public init(_ val: Int) {
        self.val = val;
    }
}

func maxDepth(root: TreeNode?) -> Int {
    guard let root = root else {
        return 0;
    }
    return max(maxDepth(root: root.left), maxDepth(root: root.right)) + 1;
}

func isValidBST(root: TreeNode?) -> Bool {
    return _helper(node: root, nil, nil);
}

private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
    guard let node = node else {
        return true;
    }
    
    // 所有右子树节点的值都必须大于根节点的值
    if let min = min, node.val <= min {
        return false;
    }
    
    // 所有左子树节点的值必须小于根节点的值
    if let max = max, node.val >= max {
        return false;
    }
    
    return _helper(node: node.left, min, node.val) && _helper(node: node.right, node.val, max);
}

let bt = TreeNode(100);
bt.left = TreeNode(99);
bt.right = TreeNode(101);
bt.left?.left = TreeNode(98);
bt.left?.right = TreeNode(97);
bt.right?.left = TreeNode(102);
bt.right?.right = TreeNode(103);
let bt1 = TreeNode(100);
bt1.left = TreeNode(101);
bt1.right = TreeNode(99);
bt1.left?.left = TreeNode(102);
bt1.left?.right = TreeNode(103);
bt1.right?.left = TreeNode(98);
bt1.right?.right = TreeNode(97);
let a = isValidBST(root: bt1);

// 用栈实现的前序遍历
func preorderTraversal(root: TreeNode?) -> [Int] {
    var res = [Int]();
    var stack = [TreeNode]();
    var node = root;
    
    while !stack.isEmpty || node != nil {
        print("\(stack)");
        if node != nil {
            res.append(node!.val);
            stack.append(node!);
            node = node!.left;
        } else {
            node = stack.removeLast().right;
        }
//        print("\(!stack.isEmpty || node != nil)")
//        print("!stack.isEmpty = \(!stack.isEmpty) - node != nil = \(node != nil)")
    }
    
    return res;
}
let preorder1 = preorderTraversal(root: bt);


func levelOrder(root: TreeNode?) -> [[Int]] {
    var res = [[Int]]();
    
    // 用数组来实现队列
    var queue = [TreeNode]();
    
    if let root = root {
        queue.append(root);
    }
    
    while queue.count > 0 {
        var size = queue.count;
        var level = [Int]();
        
        for _ in 0..<size {
            let node = queue.removeFirst();
            
            level.append(node.val);
            if let left = node.left {
                queue.append(left);
            }
            if let right = node.right {
                queue.append(right);
            }
        }
        
        res.append(level);
    }
    
    return res;
}

let level1 = levelOrder(root: bt);
